#include <stdio.h>
#include <stdlib.h>

#include "securec.h"
#include "treeUtils.h"

int len, max_size;

void inorder(struct TreeNode *root, int **nums) {
    if (root == NULL) {
        return;
    }
    inorder(root->left, nums);
    (*nums)[len++] = root->val;
    if (len == max_size) {
        max_size <<= 1; // 扩容
//        *nums = realloc(*nums, sizeof(int) * max_size);
        *nums = realloc(*nums, sizeof(int) * max_size);
    }
    inorder(root->right, nums);
}

int *findTwoSwapped(int *nums) {
    int index1 = -1;
    int index2 = -1;
    for (int i = 0; i < len - 1; ++i) {
        if (nums[i + 1] < nums[i]) {
            index2 = i + 1;

            if (index1 == -1) {// 该分支走两次结束
                index1 = i;
            } else {
                break;
            }
        }
    }
    int x = nums[index1];
    int y = nums[index2];
    int *ret = malloc(sizeof(int) * 2);
    ret[0] = x;
    ret[1] = y;
    return ret;
}

void recover(struct TreeNode *r, int count, int x, int y) {
    if (r != NULL) {
        if (r->val == x || r->val == y) {
            r->val = r->val == x ? y : x;
            if (--count == 0) {
                return;
            }
        }
        recover(r->left, count, x, y);
        recover(r->right, count, x, y);
    }
}

void recoverTree(struct TreeNode *root) {
    len = 0;
    max_size = 1;
    int *nums = malloc(sizeof(int));
    inorder(root, &nums);
    int *swapped = findTwoSwapped(nums);
    recover(root, 2, swapped[0], swapped[1]);
}

int main() {
    char str[] = "[1,3,null,null,2]";
    printf("%s\n", "start strtok string.");
    int count = 0;
    char retStrArr[100][10] = {0};
    getNum(str, retStrArr, &count);
    int numArr[9] = {0};
    for (int i = 0; i < count; ++i) {
        printf("%s\n", retStrArr[i]);
        numArr[i] = atoi(retStrArr[i]);
    }
    printf("%s\n", "end strtok string.");

    struct TreeNode *root = malloc(sizeof(struct TreeNode));
    root->val = numArr[0];
    root->left = NULL;
    root->right = NULL;
    bfsBuildTree(root, numArr, count);
    recoverTree(root);
}